// 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

// 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

//  

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
using namespace std;

// dfs
// 执行用时：
// 128 ms
// , 在所有 C++ 提交中击败了
// 60.67%
// 的用户
// 内存消耗：
// 7.3 MB
// , 在所有 C++ 提交中击败了
// 99.71%
// 的用户

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(word.size()==0){
            return true;
        }
        bool res = false;
        int hang=board.size();
        int lie = board[0].size();
        for(int i=0;i<hang;++i){
            for(int j=0;j<lie;++j){
                if(board[i][j]==word[0]){
                    cout<<"test1"<<endl;
                    res = dfs(board,word,0,i,j);
                    if(res==true){
                        return res;
                    }
                }
            }
        }
        return res;
    }

    bool dfs(vector<vector<char>>& board, string& word,int pos,int x,int y){
        if(pos >= word.size()){
            cout<<"test4"<<endl;
            return true;
        }
        if(x>=board.size() || y>=board[0].size()){
            cout<<"test5"<<endl;
            return false;
        }
        char c= board[x][y];
        if(board[x][y]==word[pos]){
            cout<<"test2"<<endl;
            board[x][y]='#';
            if(dfs(board,word,pos+1,x+1,y) || dfs(board,word,pos+1,x-1,y) || dfs(board,word,pos+1,x,y+1) || dfs(board,word,pos+1,x,y-1)){
                cout<<"test3"<<endl;
                return true;
            }
            board[x][y] = c;
        }
        return false;
    }
};